package com.easy.leetcode.dp;

/**
 * @ClassName Jump45
 * @Description 45. 跳跃游戏 II
 * @Author zheng
 * @Date 2021/11/27 15:12
 * @Version 1.0
 **/
public class Jump45 {
    public int jump(int[] nums) {
        //dp表示 跳到第i个位置，需要的最小次数
        int[] dp = new int[nums.length];
        for (int i = 1; i < nums.length; i++) {
            dp[i] = Integer.MAX_VALUE;
        }
        for (int i = 1; i < nums.length; i++) {
            //从小于i的索引中，找出能到达该位置的最小次数，作为最小次数
            for (int j = 0; j < i; j++) {
                if (j + nums[j] >= i) {
                    dp[i] = Math.min(dp[j] + 1, dp[i]);
                }
            }
        }
        return dp[nums.length - 1];
    }


    public int jump1(int[] nums) {
        //dp表示 跳到第i个位置，需要的最小次数
        int[] dp = new int[nums.length];
        for (int i = 1; i < nums.length; i++) {
            dp[i] = Integer.MAX_VALUE;
        }
        for (int i = 0; i < nums.length; i++) {
            //修正dp[i]到dp[i+nums[i]]的最小次数为dp[i]+1;
            for (int j = i; j <= i + nums[i] && j < nums.length; j++) {
                dp[j] = Math.min(dp[j], dp[i] == Integer.MAX_VALUE ? dp[i] : dp[i] + 1);
            }
        }
        return dp[nums.length - 1];
    }

    public static void main(String[] args) {
        Jump45 jump45 = new Jump45();
        System.out.println(jump45.jump1(new int[]{
                1, 2, 1, 1, 1}));
    }
}
